package com.practice.heap;

public class MinHeap {
	private int m_size;
	
	public void setSize(int size) {
		m_size = size;
	}
	
	public void heaptify(int[] A, int i) {
		int l = left(i);
		int r = right(i);
		int min = l < m_size && A[l] < A[i]? l : i;
		if (r < m_size && A[r] < A[min]) min = r;
		if (min != i) {
			int temp = A[i];
			A[i] = A[min];
			A[min] = temp;
			heaptify(A, min);
		}
	}
	
	public void buildHeap(int[] A) {
		for (int i=m_size/2; i>=0; i--) {
			heaptify(A, i);
		}
	}
	
	public void sort(int[] A) {
		setSize(A.length);
		buildHeap(A);
		for (int i=A.length; i>0; i--) {
			int temp = A[0];
			A[0] = A[i-1];
			A[i-1] = temp;
			setSize(i-1);
			buildHeap(A);
		}
	}
	
	private int parent(int i) {
		return i/2;
	}
	
	private int left(int i) {
		return i*2 + 1;
	}
	
	private int right(int i) {
		return i*2 + 2;
	}
}
